#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<string> permutation(string S) {
        vector<bool> vis(S.size(), false);
        vector<string> ret;
        string path;
        dfs(S, ret, vis, path);
        return ret;
    }

    void dfs(string& s, vector<string>& ret, vector<bool>& vis, string& path)
    {
        if (path.size() == s.size())
        {
            ret.push_back(path);
            return;
        }
        for (size_t i = 0; i < s.size(); i++)
        {
            if (vis[i] == false)
            {
                path.push_back(s[i]);
                vis[i] = true;
                dfs(s, ret, vis, path);
                path.pop_back();
                vis[i] = false;
            }
        }
    }
};